1. Field of the Invention
This invention is in the field of associative memory apparatus for rapidly translating a virtual page number of a virtual address to a physical page number of an address in a memory of a general-purpose data processing system. More particularly, the associative memory apparatus includes a pair of independently addressable validity bit arrays so that the associative memory can be quickly cleared.
2. Description of the Prior Art
Typically, in large-scale, general-purpose digital data processing systems, the central processor of such a system includes circuits for producing the addresses of instruction words in the memory of the system, for fetching instructions from memory, for preparing addresses of operands, for fetching operands from memory, for loading data into designated registers, for executing instructions, and, when the results are produced, for writing results into memory or into program-visible registers.
To increase the performance of processors and of the data processing systems of which the processors are a part, or their throughput, various modifications have been incorporated into the central processing units. To reduce the time required to obtain operands and instructions, high-speed caches located in the processor have been provided. To further speed up the systems, the systems are synchronized; i.e., a clock produces clock pulses which control each step of the operation of the central processing unit. In pipelined processors, the steps of preparing and fetching instructions or operands are overlapped to increase the system's performance.
Large-scale data processing systems frequently use a virtual memory in which the size of the virtual memory is generally so large as to impose essentially no restrictions on programmers as to the size of their programs. The size of the virtual memory, which can be equated to the number of bits defining a virtual address, is also generally much larger than the size of the physical, or actual memory of the data processing system.
Any data processing system having a virtual memory capability must have a way to translate, or map, a virtual address of a data word to its physical address. A physical address is the address in the system memory, or physical memory, of that data word. This can be accomplished by table look-up techniques, but the use of tables generally requires several clock periods, and, if the actual steps of mapping each virtual address to its corresponding physical address were required for every address that is prepared by a processor, this requirement would significantly reduce the performance, or throughput, of such a system.
To speed up the process of mapping virtual addresses to physical addresses, a paging buffer, an associative memory, may be incorporated into the processors of such systems to transform, or map, a virtual page address or number to a physical page address or number. Each successful transformation, or mapping, using a paging buffer requires only one clock period, for example. Thus, once a target physical page address of a given virtual address is determined, the target physical page number is stored or written into the paging buffer. Once this has been accomplished, the mapping of the virtual address of a given data word to its physical address can be accomplished within one clock period. A consequence of such fast mapping is that the central pipeline unit of the processor will not be broken; i.e., halted for one or more clock periods while the mapping function is performed by the paging logic of the central processor unit.
Virtual addresses (VA) can be considered as being divided into two portions, a virtual page number (VPN) and a word number. A word number is defined as the location of a data word in a page. Typically, a word number, or word address, is the lower order ten bits of a virtual address when addressing to the word level with some, or all, of the bits of higher order than the word number of a virtual address being a virtual page number (VPN). In the system in which this invention is incorporated, a VPN is a 36-bit binary number and a physical page number (PPN) is a 16-bit binary number. The 16 bits of a PPN and the ten bits of a word number constitute a physical address to the word level of a data word. A physical address is an actual address in the system memory or of a cache into which a data word corresponding to the virtual address can be written or from which it can be read. A data word can be an operand or an instruction. Typically, a data word is made up of four bytes of either 8 or 9 bits per byte. If there is a need to address to the byte or bit level, an additional 2 or 6 bits are appended to the virtual and physical word addresses to identify a byte or a bit of that data word. Such byte and bit address bits, if present, will be the least significant bits of the address.
Prior art virtual to physical address translation has been accomplished by a directly mapped associative memory which contains up to a given maximum number of the most recently used translations, or mappings, of virtual addresses to physical addresses. The paging buffer will, of course, have a given number of entries, or addresses, one for each addressable storage location of the associative memory. The data stored at each addressable memory location consists of three fields: a key field that provides the necessary association with a given VPN; a target PPN, the desired virtual to physical mapping of the given VPN; and a validity bit which denotes the presence or absence of valid information in the key and target fields of the addressed location of the associative memory. A virtual page number of a virtual address can be considered as including a lower portion, or the lower virtual page number (LVPN). The LVPN is the lower order 10 bits of a virtual page number in the preferred embodiment. The higher order bits of a VPN are the upper virtual page number (UVPN). In the preferred embodiment, the UVPN is the higher order 26 bits of a VPN. The bits of the LVPN are used as the entry to, or the address signals applied, to the address logic of a RAM chip, or chips, that comprise a paging buffer associative memory. The outputs of the associative memory include the key field, the target PPN field, and the validity bit. The key field read out of memory is compared with the bits of the UVPN of the VPN to be mapped. If they match and the validity bit is set indicating that the data stored at the addressed location is valid, or correct, then the target PPN is the proper translation of the VPN, or the target PPN is the physical page number of a physical address which can be used to fetch a data word or to write a data word into the corresponding addressable location of a memory device of the system.
There can occur situations when it is desirable to clear immediately all the entries of a paging buffer, such as when significant changes are made in the contents of the tables used to produce translations from virtual page numbers to physical page numbers. With prior art paging buffers, it was necessary to reset all the validity bits thereof to clear a paging buffer. Each addressable memory location of the paging buffer is addressed and the validity bit stored at each addressable location is reset. If there were 2.sup.10 addressable locations, for example, it would require 2.sup.10 clock periods to completely clear the buffer memory, assuming that it takes only one clock period to reset the validity bit at each addressable location of the paging buffer associative memory.